package com.mashibing.class14;


import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * 有若干个样本a、b、c、d…类型假设是V
 * 在并查集中一开始认为每个样本都在单独的集合里
 * 用户可以在任何时候调用如下两个方法：
 *        boolean isSameSet(V x, V y) : 查询样本x和样本y是否属于一个集合
 *        void union(V x, V y) : 把x和y各自所在集合的所有样本合并成一个集合
 * isSameSet和union方法的代价越低越好
 */
public class Code05_UnionFind {
    // V 是样本类型. Node 是对V包了一层.
    public static class Node<V> {
        V value;

        public Node(V v) {
            value = v;
        }
    }

    // 并查集.
    public static class UnionFind<V> {
        // V 和 它包了一层的Node 建立一一映射.
        public HashMap<V, Node<V>> nodes;
        // 谁的父亲是谁.
        public HashMap<Node<V>, Node<V>> parents;
        // Node 和 对应Node节点数的大小.
        public HashMap<Node<V>, Integer> sizeMap;

        /**
         * 并查集的初始化
         * @param values 所有并查集的样本链表的集合.
         */
        public UnionFind(List<V> values) {
            nodes = new HashMap<V, Node<V>>();
            parents = new HashMap<Node<V>, Node<V>>();
            sizeMap = new HashMap<Node<V>,Integer>();
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node); // 当前样本值 与 样本node 建立映射关系 插入nodes map中.
                parents.put(node, node); // 当前node的初始化parent为当前的node
                sizeMap.put(node, 1);// node的初始化size为1
            }
        }

        // 给你一个节点，请你往上到不能再往上，把代表返回 (代表节点.)
        public Node<V> findFather(Node<V> cur) {
            // path 记录父节点的路径.
            Stack<Node<V>> path = new Stack<Node<V>>();
            while (cur != parents.get(cur)) { // cur节点没有到顶.
                path.push(cur); // cur节点插入到path栈中.
                cur = parents.get(cur); // cur 来到它的父亲节点中
            }
            // 将path中的节点一一弹出来, 将它们的节点的父亲节点设置为cur节点.
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            return cur; // 返回cur 代表节点.
        }

        public boolean isSameSet(V a, V b) {
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a, V b) {
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                // 把 大的 和 小的 挑出来.
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> small = big == aHead ? bHead : aHead;
                //小集合的父亲设置为大集合.
                parents.put(small, big);
                // 设置大集合的 大小。
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }

        public int sets() {
            return sizeMap.size();
        }

    }
}
